package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printLevelOrder2

/**
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/description

 题型：前序遍历、后序遍历、分割数组
 * ```
 * 889. 根据前序和后序遍历构造二叉树
给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。
如果存在多个答案，您可以返回其中 任何 一个。

示例 1：
输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

示例 2:
输入: preorder = [1], postorder = [1]
输出: [1]
```
 */
class leetcode_889 {
    @Test
    fun test_1() {
        val actual: TreeNode? = constructFromPrePost(intArrayOf(1, 2, 4, 5, 3, 6, 7), intArrayOf(4, 5, 2, 6, 7, 3, 1))
        Assert.assertEquals(printLevelOrder2(actual).toString(), arrayListOf(1,2,3,4,5,6,7).toString())
    }

    @Test
    fun test_2() {
        val actual: TreeNode? = constructFromPrePost(intArrayOf(1), intArrayOf(1))
        Assert.assertEquals(printLevelOrder2(actual).toString(), arrayListOf(1).toString())
    }


    private fun constructFromPrePost(preorder: IntArray, postorder: IntArray): TreeNode? {
        if (postorder.size == 1) {
            return TreeNode(preorder[0])
        }
        return f(preorder, postorder)
    }

    private fun f(preorder: IntArray, postorder: IntArray): TreeNode? {
        /**
         * 思路：
         * 根节点在前序遍历的第一个节点
         * 找出左孩子的根节点在后序数组的index
         * 根据index 切割后序数组的左子树，右子树
         * 根据切割出的后序数组左子树来切割前序数组的左子树、右子树
         * 然后递归左子树、右子树
         */
        // 1 确认函数参数以及返回值

        // 2 确认终止条件
        if (preorder.size == 0) {
            return null
        }

        if (preorder.size == 1) {
            return TreeNode(preorder[0])
        }

        // 3 确认单层递归的处理逻辑
        // 第2步：找出根节点
        val n: Int = preorder[0]
        val root: TreeNode = TreeNode(n)

        // 第3步：找到左孩子的根节点在后序数组中的index
        val preorder = preorder.sliceArray(1 until preorder.size)
        val postorder = postorder.sliceArray(0 until postorder.size - 1)
        val leftV: Int = preorder[0]  // 左孩子的根节点
        var index: Int = 0
        for (i in 0 until postorder.size) {
            if (leftV == postorder[i]) {
                index = i
            }
        }

        // 第4步：切割后序数组
        // TODO：注意下标
        val left2 = postorder.sliceArray(0 until index + 1) // [0, index+1)
        val right2 = postorder.sliceArray(index + 1 until postorder.size) // [index+1, size)

        // 第5步：切割前序数组
        // TODO：注意下标
        val left1 = preorder.sliceArray(0 until left2.size) // [0, index+1)
        val right1 = preorder.sliceArray(left2.size until preorder.size) // [index+1, size)

        // 6 递归
        root.left = f(left1, left2)
        root.right = f(right1, right2)
        return root
    }
}